/**
 * FileName: Exercise1728.c
 * ---------------------------------------------------------------------------------------------------------------------
 * 17.28 Provide an implementation of the remove edge function `GRAPHremoveE` for the adjacency-lists
 * graph ADT implementation (Program 17.6). Note: Remember the possibility of duplicates.
 *
 *
 */
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//顶点相关
typedef struct node* link;
struct node {
    int v;
    link next;
};

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    link* adj;
};

//辅助函数声明
link NEW(int, link);
Edge EDGE(int, int);
int removeNode(link*, int);
void GRAPHshow(Graph);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//辅助函数实现
link NEW(int v, link next) {
    link x = (link) malloc(sizeof(*x));
    x->v = v;
    x->next = next;
    return x;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    printf("%d vertices, %d edges\n", G->V, G->E);
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        printf("%2d:", v);
        for (t = G->adj[v]; t != NULL; t = t->next) {
            printf(" %2d", t->v);
        }
        printf("\n");
    }
}

// 返回 1 表示成功删除，0 表示未找到
int removeNode(link *head, int target_v) {
    link curr = *head;
    link prev = NULL;

    while (curr != NULL && curr->v != target_v) {
        prev = curr;
        curr = curr->next;
    }

    if (curr == NULL) { // 未找到目标节点
        return 0;
    }

    // 找到目标节点 curr
    if (prev == NULL) { // 目标节点是头节点
        *head = curr->next;
    } else { // 目标节点不是头节点
        prev->next = curr->next;
    }
    free(curr); // 释放节点内存
    return 1; // 成功删除
}


//图操作函数实现
Graph GRAPHinit(int V) {
    int v;
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = (link*) malloc(V * sizeof(link));
    for (v = 0; v < V; v++) {
        G->adj[v] = NULL;
    }
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    G->adj[v] = NEW(w, G->adj[v]);
    G->adj[w] = NEW(v, G->adj[w]);
    G->E++;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    int removeCount = 0;

    removeCount += removeNode(&G->adj[v], w);
    removeCount += removeNode(&G->adj[w], v);

    if (removeCount == 2) {
        G->E--;
    }
}
int GRAPHedges(Edge a[], Graph G) {
    int E;
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            if (v < t->v) {
                a[E++] = EDGE(v, t->v);
            }
        }
    }

    return E;
}
Graph GRAPHcopy(Graph G) {
    //TODO
}
void GRAPHdestroy(Graph G) {
    //TODO
}

//测试函数声明
void test_show();
void test_remove_edge();

int main(int argc, char *argv[]) {
    test_remove_edge();
    return 0;
}

//测试函数实现
void test_show() {
    int V = 10;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(3, 7);
    Edge edge2 = EDGE(1, 4);
    Edge edge3 = EDGE(7, 8);
    Edge edge4 = EDGE(0, 5);
    Edge edge5 = EDGE(5, 2);
    Edge edge6 = EDGE(3, 8);
    Edge edge7 = EDGE(2, 9);
    Edge edge8 = EDGE(0, 6);
    Edge edge9 = EDGE(4, 9);
    Edge edge10 = EDGE(2, 6);
    Edge edge11 = EDGE(6, 4);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);
    GRAPHinsertE(G, edge11);

    GRAPHshow(G);
}

void test_remove_edge() {
    int V = 10;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(3, 7);
    Edge edge2 = EDGE(1, 4);
    Edge edge3 = EDGE(7, 8);
    Edge edge4 = EDGE(0, 5);
    Edge edge5 = EDGE(5, 2);
    Edge edge6 = EDGE(3, 8);
    Edge edge7 = EDGE(2, 9);
    Edge edge8 = EDGE(0, 6);
    Edge edge9 = EDGE(4, 9);
    Edge edge10 = EDGE(2, 6);
    Edge edge11 = EDGE(6, 4);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);
    GRAPHinsertE(G, edge11);

    GRAPHshow(G);

    GRAPHremoveE(G, edge1);

    GRAPHshow(G);

    GRAPHremoveE(G, edge1);

    GRAPHshow(G);
}
